/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package mamayukero.logic.pathfinding;

import java.awt.Point;
import java.util.ArrayList;
import java.util.LinkedList;
import mamayukero.debug.LogContainer;
import mamayukero.problem.environment.map.Map;
import mamayukero.problem.environment.map.Path;

public class BFS extends PathFindingBase {

	Node startNode,endNode;
	public BFS(Map pMap) 
	{
		super(pMap);
                log = new LogContainer("BFS");
	}
        
	@Override
	public Path solve(Point start, Point end) {
		this.start = start;
		this.end = end;
		path = new Path(start,end);
		pathlist.clear();
		startNode = new Node(start);
		startNode.parent = null;
		endNode = new Node(end);
		endNode.parent = null;
                log.append("Mencari jalan dari [" + start.x + "," + start.y + "]" + " ke " + "[" + end.x + "," + end.y + "]");
		path.setPoint(solveBFS());
                StringBuilder pathString = new StringBuilder("Menemukan jalan : ");
                for (Point p: path.point) {
                    pathString.append("[").append(p.x).append(",").append(p.y).append("]");
                }
                log.append(pathString.toString());
		return path;
	}
	
	
	class Node
	{
		Point mPoint;	
		Node parent;	
		ArrayList<Node> children;
		
		Node(Point pPoint)
		{
			mPoint = pPoint.getLocation();
		}
		Node getNode()
		{
			return new Node(mPoint);
		}

		@Override
		public String toString() {
			return "Node{" + "mPoint=" + mPoint + '}';
		}
	}
	
	private ArrayList<Point> constructPath(Node pNode)
	{
		LinkedList<Point> tPath = new LinkedList<Point>();
		while (pNode.parent != null)
		{
			tPath.addFirst(pNode.mPoint);
			pNode = pNode.parent;
		}
		tPath.addFirst(pNode.mPoint);
		return new  ArrayList<Point>(tPath);
	}
			
	/**
	 * kepikiran buat array dari array
	 * ato linked list
	 * @param p
	 * @return solusi
	 */
	private ArrayList<Point> solveBFS()
	{
		//solution path
		ArrayList<Point> sol = new ArrayList<Point>();
		
		//list of visited points
		ArrayList<Point> visitedPs = new ArrayList<Point>();
		
		//queue for node expansion sequence
		ArrayList<Node> tQueue = new ArrayList<Node>();
		
		//moveable points for each expansion, not including already visited points
		ArrayList<Node> moveableNs; 
		
		Node tCurN = startNode;
		boolean isSolFound = false;
		
		tQueue.add(tCurN.getNode());
		while (!tQueue.isEmpty() && !isSolFound)
		{
			tCurN = tQueue.remove(0);
			//System.out.println("tCurN: " + tCurN.toString());			
			
			if (!isSol(tCurN)) {
				//add current point to visited points
				visitedPs.add(tCurN.mPoint.getLocation());
				
				//expand current position
				moveableNs = notVisitedNodes(tCurN, visitedPs);
				
				//add children into queue
				tQueue.addAll(moveableNs);
						
			} else {
				//goal found
				isSolFound = true;
				sol = constructPath(tCurN);
			}
		}
		return sol;
	}
	
	private ArrayList<Node> notVisitedNodes(Node pCurN, ArrayList<Point> pVisitedPs)
	{
		//System.out.println("notVisitedNodes()");
		ArrayList<Point> tMoveablePs = whereToGo(pCurN.mPoint.x, pCurN.mPoint.y, map);
		pCurN.children = new ArrayList<Node>();
		
		boolean found=false;
		int i=0;
		while (!found && i<tMoveablePs.size())
		{
			if (pVisitedPs.contains(tMoveablePs.get(i))) {
				found = true;
			}
			i++;
		}
		if (found) {
			i--;
			tMoveablePs.remove(i);
		}
		
		i=0;
		for (Point p : tMoveablePs)
		{
			pCurN.children.add(new Node(p));
			pCurN.children.get(i).parent = pCurN;
			i++;
		}
		
		return pCurN.children;
	}
	
	private boolean isSol(Node pNode)
	{
		return pNode.mPoint.equals(endNode.mPoint);
	}
}
